import java.util.ArrayList;
import java.util.Collections;

public class Merge 
{
	public static int num = 8;
	public static ArrayList<Integer> list = new ArrayList<Integer> (num);
	
	public static ArrayList<Integer> mergesort(ArrayList<Integer> arr)
	{
		int x = arr.size();
		ArrayList<Integer> left = new ArrayList<Integer> (x/2);
		ArrayList<Integer> right = new ArrayList<Integer> (x/2);
		ArrayList<Integer> result=new ArrayList<Integer> (x);
	    if (arr.size() <= 1)
	        return arr;
	    else
	    {
		        int center = arr.size() / 2;
		        for(int i = 0 ; i < center;i++)
		        {
		        	left.add(arr.get(i));
		        }
		        System.out.println(left);
		        for(int i = center; i< arr.size();i++)
		        {
		        	right.add(arr.get(i));
		        }
		        System.out.println(right);
		        left = mergesort(left);
		        right = mergesort(right);
		        result = merge(left, right);
		        return result;
	    }
	}
	public static ArrayList<Integer> merge(ArrayList<Integer> left,ArrayList<Integer> right)
	{
		ArrayList<Integer>  result = new ArrayList<Integer> (left.size() + right.size());
		int ind=0;
	    while (left.size() > 0 && right.size() > 0)
	    {
	        if (left.get(0) <= right.get(0))
	        {
	            result.add(ind, left.get(0));
	            left.remove(0);
	            ind++;
	        }
	        else
	        {
	            result.add(ind, right.get(0));
	            right.remove(0);
	            ind++;
	        }
	    }
	    if (left.size() > 0)
	    	result.addAll(ind, left);
	    if (right.size() > 0)
	    	result.addAll(ind, right);
	    return result;
	}

	
	public static void main(String[] args) 
	{
		for (int i = 0; i < num; i++)
		
		{
			list.add(i);
		}
		Collections.shuffle(list);
		System.out.println(list);
		list = mergesort(list);
		System.out.println(list);
	}	
		
}
